from collections import deque


class TreeNode:
    def __init__(self):
        self.lchild = None
        self.rchild = None
        # 如果有需要，可以在这里添加其他数据字段


def create_tree():
    # 创建一个简单的二叉树
    #        root
    #       /   \
    #     node1 node2
    #            /
    #          node3
    root = TreeNode()
    node1 = TreeNode()
    node2 = TreeNode()
    node3 = TreeNode()
    node4=TreeNode()


    root.lchild = node1
    root.rchild = node2
    node2.lchild = node3
    node2.rchild=node4
    return root


def BTWidth(root):
    if not root:
        return 0

    queue = deque([(root, 1)])  # (node, level)
    max_width = 0
    current_level = 1
    next_level_count = 1

    while queue:
        node, level = queue.popleft()

        # 到达新一层时，更新最大宽度（如果需要）
        if level > current_level:
            max_width = next_level_count
            current_level = level
            next_level_count = 0

            # 将子节点加入队列，并更新下一层的节点数
        if node.lchild:
            queue.append((node.lchild, level + 1))
            next_level_count += 1
        if node.rchild:
            queue.append((node.rchild, level + 1))
            next_level_count += 1

            # 检查最后一层是否有更宽的
    if next_level_count > max_width:
        max_width = next_level_count

    return max_width


# 主函数
if __name__ == "__main__":
    root = create_tree()
    width = BTWidth(root)
    print(f"The width of the binary tree is: {width}")